package com.nowcoder.code.hjnc;

import java.util.Arrays;

public class NC92 {

    static int[][] dp = null;
    static int[][] dp2 = null;
    static char[] cs1 = null;
    static char[] cs2 = null;


    public int longestCommonSubsequence(String text1, String text2) {
        cs1 = text1.toCharArray();
        cs2 = text2.toCharArray();
        dp = new int[cs1.length + 1][cs2.length + 1];
        dp2 = new int[cs1.length + 1][cs2.length + 1];

        for (int i = 1; i <= cs1.length; i++) {
            for (int j = 1; j <= cs2.length; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    dp2[i][j] = 3;
                } else {
                    if (dp[i][j - 1] > dp[i - 1][j]) {
                        dp[i][j] = dp[i][j - 1];
                        dp2[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j];
                        dp2[i][j] = 2;
                    }
                }
            }
        }

        return dp[cs1.length][cs2.length];
    }

    public String LCS(String s1, String s2) {
        int i1 = longestCommonSubsequence(s1, s2);
        if (i1 == 0) {
            return "-1";
        }
        StringBuilder sb = new StringBuilder();
        int i = cs1.length, j = cs2.length;
        while (i > 0 && j > 0) {

            if (dp2[i][j] == 3) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    sb.insert(0, cs1[i - 1]);
                }
                i--;
                j--;
            } else if (dp2[i][j] == 1) {
                j--;
            } else {
                i--;
            }


        }

        return sb.toString();
    }

    public static void main(String[] args) {

        System.out.println(new NC92().LCS("1A2C3D4B56", "B1D23A456A"));

        System.out.println("    " + Arrays.toString(cs2));
        System.out.println(" " + Arrays.toString(dp[0]));

        for (int i = 1; i < dp.length; i++) {
            System.out.println(cs1[i - 1] + Arrays.toString(dp[i]));
        }
    }

}
